// 红黑树实现
// 红黑树是一种自平衡的二叉搜索树，满足以下性质：
// 1. 每个节点要么是红色，要么是黑色
// 2. 根节点是黑色
// 3. 每个叶子节点（NIL节点）是黑色
// 4. 如果一个节点是红色，则它的两个子节点都是黑色
// 5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

class RBNode {
    constructor(key, value, color = 'RED') {
        this.key = key;
        this.value = value;
        this.color = color; // 'RED' or 'BLACK'
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    // 判断节点是否为红色
    isRed() {
        return this.color === 'RED';
    }

    // 判断节点是否为黑色
    isBlack() {
        return this.color === 'BLACK';
    }

    // 将节点颜色设置为红色
    setRed() {
        this.color = 'RED';
    }

    // 将节点颜色设置为黑色
    setBlack() {
        this.color = 'BLACK';
    }
}

class RedBlackTree {
    constructor() {
        this.NIL = new RBNode(null, null, 'BLACK'); // 哨兵节点
        this.root = this.NIL;
        this.size = 0;
    }

    // 左旋操作
    leftRotate(x) {
        const y = x.right;
        x.right = y.left;
        
        if (y.left !== this.NIL) {
            y.left.parent = x;
        }
        
        y.parent = x.parent;
        
        if (x.parent === null) {
            this.root = y;
        } else if (x === x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        
        y.left = x;
        x.parent = y;
    }

    // 右旋操作
    rightRotate(y) {
        const x = y.left;
        y.left = x.right;
        
        if (x.right !== this.NIL) {
            x.right.parent = y;
        }
        
        x.parent = y.parent;
        
        if (y.parent === null) {
            this.root = x;
        } else if (y === y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        
        x.right = y;
        y.parent = x;
    }

    // 插入节点
    insert(key, value) {
        const newNode = new RBNode(key, value);
        newNode.left = this.NIL;
        newNode.right = this.NIL;
        
        let y = null;
        let x = this.root;
        
        // 找到插入位置
        while (x !== this.NIL) {
            y = x;
            if (key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        
        newNode.parent = y;
        if (y === null) {
            this.root = newNode;
        } else if (key < y.key) {
            y.left = newNode;
        } else {
            y.right = newNode;
        }
        
        this.size++;
        
        // 如果新节点是根节点，直接设置为黑色
        if (newNode.parent === null) {
            newNode.setBlack();
            return;
        }
        
        // 如果祖父节点不存在，不需要修复
        if (newNode.parent.parent === null) {
            return;
        }
        
        // 修复红黑树性质
        this.insertFixup(newNode);
    }

    // 插入后修复红黑树性质
    insertFixup(z) {
        while (z.parent !== null && z.parent.isRed()) {
            if (z.parent === z.parent.parent.left) {
                const y = z.parent.parent.right;
                
                // 情况1：叔叔节点是红色
                if (y.isRed()) {
                    z.parent.setBlack();
                    y.setBlack();
                    z.parent.parent.setRed();
                    z = z.parent.parent;
                } else {
                    // 情况2：z是右孩子
                    if (z === z.parent.right) {
                        z = z.parent;
                        this.leftRotate(z);
                    }
                    // 情况3：z是左孩子
                    z.parent.setBlack();
                    z.parent.parent.setRed();
                    this.rightRotate(z.parent.parent);
                }
            } else {
                const y = z.parent.parent.left;
                
                // 情况1：叔叔节点是红色
                if (y.isRed()) {
                    z.parent.setBlack();
                    y.setBlack();
                    z.parent.parent.setRed();
                    z = z.parent.parent;
                } else {
                    // 情况2：z是左孩子
                    if (z === z.parent.left) {
                        z = z.parent;
                        this.rightRotate(z);
                    }
                    // 情况3：z是右孩子
                    z.parent.setBlack();
                    z.parent.parent.setRed();
                     this.leftRotate(z.parent.parent);
                }
            }
            
            if (z === this.root) {
                break;
            }
        }
        
        this.root.setBlack();
    }

    // 查找节点
    search(key) {
        return this.searchNode(this.root, key);
    }

    searchNode(node, key) {
        if (node === this.NIL || key === node.key) {
            return node;
        }
        
        if (key < node.key) {
            return this.searchNode(node.left, key);
        } else {
            return this.searchNode(node.right, key);
        }
    }

    // 删除节点
    delete(key) {
        const z = this.search(key);
        if (z === this.NIL) {
            return false; // 节点不存在
        }
        
        let y = z;
        let yOriginalColor = y.color;
        let x;
        
        if (z.left === this.NIL) {
            x = z.right;
            this.transplant(z, z.right);
        } else if (z.right === this.NIL) {
            x = z.left;
            this.transplant(z, z.left);
        } else {
            y = this.minimumNode(z.right);
            yOriginalColor = y.color;
            x = y.right;
            
            if (y.parent === z) {
                x.parent = y;
            } else {
                this.transplant(y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }
            
            this.transplant(z, y);
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color;
        }
        
        this.size--;
        
        if (yOriginalColor === 'BLACK') {
            this.deleteFixup(x);
        }
        
        return true;
    }

    // 节点替换操作
    transplant(u, v) {
        if (u.parent === null) {
            this.root = v;
        } else if (u === u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        v.parent = u.parent;
    }

    // 删除后修复红黑树性质
    deleteFixup(x) {
        while (x !== this.root && x.isBlack()) {
            if (x === x.parent.left) {
                let w = x.parent.right;
                
                // 情况1：兄弟节点是红色
                if (w.isRed()) {
                    w.setBlack();
                    x.parent.setRed();
                    this.leftRotate(x.parent);
                    w = x.parent.right;
                }
                
                // 情况2：兄弟节点的两个子节点都是黑色
                if (w.left.isBlack() && w.right.isBlack()) {
                    w.setRed();
                    x = x.parent;
                } else {
                    // 情况3：兄弟节点的右子节点是黑色，左子节点是红色
                    if (w.right.isBlack()) {
                        w.left.setBlack();
                        w.setRed();
                        this.rightRotate(w);
                        w = x.parent.right;
                    }
                    
                    // 情况4：兄弟节点的右子节点是红色
                    w.color = x.parent.color;
                    x.parent.setBlack();
                    w.right.setBlack();
                    this.leftRotate(x.parent);
                    x = this.root;
                }
            } else {
                let w = x.parent.left;
                
                // 情况1：兄弟节点是红色
                if (w.isRed()) {
                    w.setBlack();
                    x.parent.setRed();
                    this.rightRotate(x.parent);
                    w = x.parent.left;
                }
                
                // 情况2：兄弟节点的两个子节点都是黑色
                if (w.right.isBlack() && w.left.isBlack()) {
                    w.setRed();
                    x = x.parent;
                } else {
                    // 情况3：兄弟节点的左子节点是黑色，右子节点是红色
                    if (w.left.isBlack()) {
                        w.right.setBlack();
                        w.setRed();
                        this.leftRotate(w);
                        w = x.parent.left;
                    }
                    
                    // 情况4：兄弟节点的左子节点是红色
                    w.color = x.parent.color;
                    x.parent.setBlack();
                    w.left.setBlack();
                    this.rightRotate(x.parent);
                    x = this.root;
                }
            }
        }
        
        x.setBlack();
    }

    // 中序遍历
    inOrderTraversal(callback) {
        this.inOrder(this.root, callback);
    }

    inOrder(node, callback) {
        if (node !== this.NIL) {
            this.inOrder(node.left, callback);
            callback(node.key, node.value, node.color);
            this.inOrder(node.right, callback);
        }
    }

    // 获取最小值
    minimum() {
        return this.minimumNode(this.root);
    }

    minimumNode(node) {
        while (node.left !== this.NIL) {
            node = node.left;
        }
        return node;
    }

    // 获取最大值
    maximum() {
        return this.maximumNode(this.root);
    }

    maximumNode(node) {
        while (node.right !== this.NIL) {
            node = node.right;
        }
        return node;
    }

    // 获取树的高度
    height() {
        return this.getHeight(this.root);
    }

    getHeight(node) {
        if (node === this.NIL) {
            return 0;
        }
        return Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
    }

    // 验证红黑树性质
    validate() {
        if (this.root.isRed()) {
            throw new Error('根节点必须是黑色');
        }
        
        const blackCount = this.validateNode(this.root);
        console.log('红黑树验证通过，黑色节点高度:', blackCount);
        return true;
    }

    validateNode(node) {
        if (node === this.NIL) {
            return 1; // NIL节点是黑色
        }
        
        // 检查红色节点的子节点必须是黑色
        if (node.isRed()) {
            if (node.left.isRed() || node.right.isRed()) {
                throw new Error('红色节点的子节点必须是黑色');
            }
        }
        
        const leftBlackCount = this.validateNode(node.left);
        const rightBlackCount = this.validateNode(node.right);
        
        // 检查左右子树的黑色节点数量是否相等
        if (leftBlackCount !== rightBlackCount) {
            throw new Error('从节点到叶子的路径黑色节点数量不相等');
        }
        
        return leftBlackCount + (node.isBlack() ? 1 : 0);
    }

    // 打印树结构（用于调试）
    printTree() {
        this.printNode(this.root, '', true);
    }

    printNode(node, indent, isLast) {
        if (node !== this.NIL) {
            process.stdout.write(indent);
            if (isLast) {
                process.stdout.write('└── ');
                indent += '    ';
            } else {
                process.stdout.write('├── ');
                indent += '│   ';
            }
            
            const color = node.isRed() ? 'R' : 'B';
            console.log(`${node.key}(${color})`);
            
            this.printNode(node.left, indent, false);
            this.printNode(node.right, indent, true);
        }
    }

    // 判断树是否为空
    isEmpty() {
        return this.root === this.NIL;
    }

    // 清空树
    clear() {
        this.root = this.NIL;
        this.size = 0;
    }

    // 获取前驱节点
    predecessor(key) {
        const node = this.search(key);
        if (node === this.NIL) {
            return this.NIL;
        }
        
        if (node.left !== this.NIL) {
            return this.maximumNode(node.left);
        }
        
        let parent = node.parent;
        let current = node;
        while (parent !== null && current === parent.left) {
            current = parent;
            parent = parent.parent;
        }
        return parent !== null ? parent : this.NIL;
    }

    // 获取后继节点
    successor(key) {
        const node = this.search(key);
        if (node === this.NIL) {
            return this.NIL;
        }
        
        if (node.right !== this.NIL) {
            return this.minimumNode(node.right);
        }
        
        let parent = node.parent;
        let current = node;
        while (parent !== null && current === parent.right) {
            current = parent;
            parent = parent.parent;
        }
        return parent !== null ? parent : this.NIL;
    }

    // 层序遍历
    levelOrderTraversal(callback) {
        if (this.root === this.NIL) {
            return;
        }
        
        const queue = [this.root];
        while (queue.length > 0) {
            const node = queue.shift();
            callback(node.key, node.value, node.color);
            
            if (node.left !== this.NIL) {
                queue.push(node.left);
            }
            if (node.right !== this.NIL) {
                queue.push(node.right);
            }
        }
    }
}

// 示例用法
function exampleUsage() {
    const rbTree = new RedBlackTree();
    
    // 插入一些数据
    const data = [10, 20, 30, 15, 25, 5, 35, 40, 45, 50];
    data.forEach((key, index) => {
        rbTree.insert(key, `value${index}`);
    });
    
    console.log('=== 初始红黑树 ===');
    console.log('红黑树大小:', rbTree.size);
    console.log('树高度:', rbTree.height());
    
    // 验证红黑树性质
    try {
        rbTree.validate();
        console.log('红黑树性质验证通过!');
    } catch (error) {
        console.error('验证失败:', error.message);
    }
    
    // 中序遍历
    console.log('\n中序遍历:');
    rbTree.inOrderTraversal((key, value, color) => {
        console.log(`Key: ${key}, Value: ${value}, Color: ${color}`);
    });
    
    // 查找节点
    const found = rbTree.search(25);
    if (found !== rbTree.NIL) {
        console.log('\n找到节点:', found.key, found.value);
    }
    
    // 打印树结构
    console.log('\n树结构:');
    rbTree.printTree();
    
    // 测试删除操作
    console.log('\n=== 测试删除操作 ===');
    
    // 删除节点20
    console.log('删除节点20:', rbTree.delete(20) ? '成功' : '失败');
    console.log('删除后树大小:', rbTree.size);
    
    // 验证删除后的性质
    try {
        rbTree.validate();
        console.log('删除后红黑树性质验证通过!');
    } catch (error) {
        console.error('删除后验证失败:', error.message);
    }
    
    console.log('\n删除后的中序遍历:');
    rbTree.inOrderTraversal((key, value, color) => {
        console.log(`Key: ${key}, Value: ${value}, Color: ${color}`);
    });
    
    console.log('\n删除后的树结构:');
    rbTree.printTree();
    
    // 删除不存在的节点
    console.log('\n删除不存在的节点100:', rbTree.delete(100) ? '成功' : '失败');
    
    // 继续删除几个节点
    console.log('删除节点5:', rbTree.delete(5) ? '成功' : '失败');
    console.log('删除节点35:', rbTree.delete(35) ? '成功' : '失败');
    console.log('最终树大小:', rbTree.size);
    
    // 最终验证
    try {
        rbTree.validate();
        console.log('最终红黑树性质验证通过!');
    } catch (error) {
        console.error('最终验证失败:', error.message);
    }
    
    console.log('\n最终中序遍历:');
    rbTree.inOrderTraversal((key, value, color) => {
        console.log(`Key: ${key}, Value: ${value}, Color: ${color}`);
    });
    
    // 测试新添加的方法
    console.log('\n=== 测试额外方法 ===');
    console.log('树是否为空:', rbTree.isEmpty());
    
    // 测试前驱和后继
    const succ = rbTree.successor(30);
    if (succ !== rbTree.NIL) {
        console.log('30的后继节点:', succ.key);
    }
    
    const pred = rbTree.predecessor(30);
    if (pred !== rbTree.NIL) {
        console.log('30的前驱节点:', pred.key);
    }
    
    // 测试层序遍历
    console.log('\n层序遍历:');
    rbTree.levelOrderTraversal((key, value, color) => {
        console.log(`Key: ${key}, Value: ${value}, Color: ${color}`);
    });
    
    // 测试清空
    rbTree.clear();
    console.log('\n清空后树大小:', rbTree.size);
    console.log('清空后树是否为空:', rbTree.isEmpty());
}

// 导出模块
if (typeof module !== 'undefined' && module.exports) {
    module.exports = { RBNode, RedBlackTree };
}

// 运行示例
if (require.main === module) {
    exampleUsage();
}